#include <iostream>
#include <fstream>
#include <map>
#include <set>
#include <unordered_set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <iterator>
using namespace std;

#define EPSILON -1
#define CLOSURE '*'
#define OPEN_PAREN '('
#define CLOSE_PAREN ')'
#define OR '+'
#define CONCAT '.'

struct Token
{
	string value;
	string type;
};

class State
{
public:
	set<State*> NFAStates;
	multimap<char, State*> Transition;
	int StateID;
	bool Accept;
	bool Marked;
	int GroupID;

	State() : StateID(-1), Accept(false) {};
	State(int nID) : StateID(nID), Accept(false), GroupID(0) {};
	State(set<State*> NFAState, int nID)
	{
		NFAStates = NFAState;
		StateID = nID;
		Accept = false;
		GroupID = 0;
		set<State*>::iterator iter;
		for (iter = NFAState.begin(); iter != NFAState.end(); ++iter)
		{
			if ((*iter)->Accept)
			{
				Accept = true;
			}
		}
	}
	State(const State& other)
	{
		*this = other;
	}
	~State()
	{
		NFAStates.clear();
		Transition.clear();
	}

	void AddTransition(char inputCh, State* pState)
	{
		Transition.insert(make_pair(inputCh, pState));
	}

	void GetTransition(char inputCh, vector<State*>& States)
	{
		States.clear();
		multimap<char, State*>::iterator iter;
		for (iter = Transition.lower_bound(inputCh); iter != Transition.upper_bound(inputCh); ++iter)
		{
			State* pState = iter->second;
			States.push_back(pState);
		}
	}

	State& operator=(const State& other)
	{
		this->Transition = other.Transition;
		this->StateID = other.StateID;
		this->NFAStates = other.NFAStates;
		return *this;
	}

	bool operator==(const State& other)
	{
		if (NFAStates.empty())
			return (StateID == other.StateID);
		else
			return (NFAStates == other.NFAStates);
	}

	set<State*>& GetNFAState()
	{
		return NFAStates;
	}
};

vector<State*> NFATable;
vector<State*> DFATable;

class LexAnalyzer
{
public:
	void LoadInputFile();
	void InputInfixRE();
	void PreProcessInfixRE();
	void InfixREtoPostfixRE();
	bool TakesPrecedence(char topStack, char ch);
	bool PostfixREtoNFA();
	bool Matching(string s);
	void CreateOneCharNFA(char ch);
	bool PopTable(vector<State*>& NFATable);
	bool Concat();
	bool Closure();
	bool Or();
	bool IsOperator(char inputCh);
	void EpsilonClosure(set<State*> startSet, set<State*>& result);
	void Move(char chInput, set<State*> NFAState, set<State*>& Result);
	void NFAtoDFA();
	void Scanner();
	void Output();
	string RemoveBracket(string s);

	string str;
	vector<string> RE;
	string InfixRE;
	string PostfixRE;
	vector<Token> Tokens;
	stack<vector<State*>> ThompsonStack;
	set<char> InputSet;
	char CurPreProcChar;
	int NextStateID;
};

void LexAnalyzer::LoadInputFile()
{
	fstream file;
	string temp;

	file.open("input.cpp", ios::in);

	if (!file)
	{
		cout << "no program file available\n";
		system("pause");
		exit(0);
	}

	while (!file.eof())
	{
		str += file.get();
	}
	str.pop_back();
}

void LexAnalyzer::InputInfixRE()
{
	fstream file;
	string temp;

	file.open("RegularExpression.txt", ios::in);

	if (!file)
	{
		cout << "no RE file available\n";
		system("pause");
		exit(0);
	}

	while (!file.eof())
	{
		file >> temp;
		RE.push_back(temp);
	}
}

void LexAnalyzer::PreProcessInfixRE()
{
	int i;
	for (i = 0; i < RE.size() - 1; i++)
	{
		InfixRE += "(" + RE[i] + ")" + "+";
	}
	InfixRE += "(" + RE[i] + ")";

	while (InfixRE.find("[") != string::npos)
	{
		InfixRE = RemoveBracket(InfixRE);
	}
}

void LexAnalyzer::InfixREtoPostfixRE()
{
	stack<char> OperatorStack;
	char TopSymbol, Symbol;
	int k;

	for (k = 0; k < InfixRE.size(); k++)
	{
		Symbol = InfixRE[k];

		if (Symbol == '~')
		{
			PostfixRE = PostfixRE + Symbol;
			k++;
			Symbol = InfixRE[k];
			PostfixRE = PostfixRE + Symbol;
		}
		else if (Symbol == '(')
		{
			OperatorStack.push(Symbol);
		}
		else if (Symbol == ')')
		{
			while (OperatorStack.top() != '(')
			{
				TopSymbol = OperatorStack.top();
				OperatorStack.pop();
				PostfixRE = PostfixRE + TopSymbol;
			}
			OperatorStack.pop();
		}
		else if (IsOperator(Symbol))
		{
			if (OperatorStack.empty() || (!(OperatorStack.empty()) && TakesPrecedence(OperatorStack.top(), Symbol)))
			{
				OperatorStack.push(Symbol);
			}
			else
			{
				while (!(OperatorStack.empty()) && !TakesPrecedence(OperatorStack.top(), Symbol))
				{
					TopSymbol = OperatorStack.top();
					OperatorStack.pop();
					PostfixRE = PostfixRE + TopSymbol;
				}
				OperatorStack.push(Symbol);
			}
		}
		else
		{
			PostfixRE = PostfixRE + Symbol;
		}
	}
	while (!OperatorStack.empty())
	{
		TopSymbol = OperatorStack.top();
		OperatorStack.pop();
		PostfixRE = PostfixRE + TopSymbol;
	}
	PostfixRE += "\0";
}

bool LexAnalyzer::IsOperator(char Ch)
{
	if (Ch == CLOSURE || Ch == OR || Ch == OPEN_PAREN || Ch == CLOSE_PAREN || Ch == CONCAT)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool LexAnalyzer::TakesPrecedence(char topStack, char ch)
{
	if (topStack == '(')
	{
		return true;
	}
	char operators[6] = { '+', '.', '*', '(' };

	int i, j;
	for (i = 0; i < strlen(operators); i++)
	{
		if (operators[i] == topStack)
			break;
	}
	for (j = 0; j < strlen(operators); j++)
	{
		if (operators[j] == ch)
			break;
	}

	if (i >= j)
		return false;
	else
		return true;
}

string LexAnalyzer::RemoveBracket(string s)
{
	string::size_type startPos, endPos, separatorPos;
	string ReplacedStr;

	startPos = s.find_first_of("[");
	endPos = s.find_first_of("]");
	separatorPos = s.find_first_of("-");

	if (startPos == string::npos || endPos == string::npos)
		return s;

	ReplacedStr += s.substr(0, startPos);
	ReplacedStr.push_back('(');
	string result = s.substr(startPos + 1, endPos - startPos - 1);
	char first = result[0];
	char last = result[result.size() - 1];

	if (separatorPos != string::npos)
	{
		while (first < last)
		{
			ReplacedStr.push_back(first);
			ReplacedStr += "+";
			first++;
		}
		ReplacedStr.push_back(first);
	}
	else
	{
		startPos++;
		while (startPos != endPos - 1)
		{
			ReplacedStr.push_back(s[startPos]);
			ReplacedStr += "+";
			startPos++;
		}
		ReplacedStr.push_back(s[endPos - 1]);
	}
	ReplacedStr.push_back(')');
	ReplacedStr += s.substr(endPos + 1, s.size() - endPos);

	return ReplacedStr;
}

bool LexAnalyzer::PostfixREtoNFA()
{
	for (int i = 0; i < (int)PostfixRE.size(); i++)
	{
		char Ch = PostfixRE[i];

		if (!IsOperator(Ch))
		{
			if (Ch == '~')
			{
				i++;
				Ch = PostfixRE[i];
			}
			CreateOneCharNFA(Ch);
		}
		else if (IsOperator(Ch))
		{
			if (Ch == '.')
				Concat();
			else if (Ch == '*')
				Closure();
			else if (Ch == '+')
				Or();
		}
	}
	PopTable(NFATable);
	NFATable[NFATable.size() - 1]->Accept = true;
	return true;
}

void LexAnalyzer::CreateOneCharNFA(char ch)
{
	State* s0 = new State(NextStateID++);
	State* s1 = new State(NextStateID++);

	s0->AddTransition(ch, s1);

	vector<State*> NewSubTable;
	NewSubTable.push_back(s0);
	NewSubTable.push_back(s1);
	ThompsonStack.push(NewSubTable);

	InputSet.insert(ch);
}

bool LexAnalyzer::PopTable(vector<State*>& NFATable)
{
	if (ThompsonStack.size() > 0)
	{
		NFATable = ThompsonStack.top();
		ThompsonStack.pop();
		return true;
	}
	return false;
}

bool LexAnalyzer::Concat()
{
	vector<State*> LeftTable, RightTable;

	if (!PopTable(RightTable) || !PopTable(LeftTable))
		return false;

	(*(LeftTable.rbegin()))->AddTransition(EPSILON, *(RightTable.begin()));
	LeftTable.insert(LeftTable.end(), RightTable.begin(), RightTable.end());
	ThompsonStack.push(LeftTable);

	return true;
}

bool LexAnalyzer::Closure()
{
	vector<State*> PrevTable;

	if (!PopTable(PrevTable))
		return false;

	State* LeftTable = new State(NextStateID++);
	State* RightTable = new State(NextStateID++);

	LeftTable->AddTransition(EPSILON, RightTable);
	LeftTable->AddTransition(EPSILON, *(PrevTable.begin()));
	(*(PrevTable.rbegin()))->AddTransition(EPSILON, RightTable);
	(*(PrevTable.rbegin()))->AddTransition(EPSILON, *(PrevTable.begin()));

	PrevTable.insert(PrevTable.begin(), LeftTable);
	PrevTable.push_back(RightTable);

	ThompsonStack.push(PrevTable);

	return true;
}

bool LexAnalyzer::Or()
{
	vector<State*> UpperTable, LowerTable;

	if (!PopTable(LowerTable) || !PopTable(UpperTable))
		return false;

	State* LeftTable = new State(NextStateID++);
	State* RightTable = new State(NextStateID++);

	LeftTable->AddTransition(EPSILON, *(UpperTable.begin()));
	LeftTable->AddTransition(EPSILON, *(LowerTable.begin()));
	(*(UpperTable.rbegin()))->AddTransition(EPSILON, RightTable);
	(*(LowerTable.rbegin()))->AddTransition(EPSILON, RightTable);

	LowerTable.push_back(RightTable);
	UpperTable.insert(UpperTable.begin(), LeftTable);
	UpperTable.insert(UpperTable.end(), LowerTable.begin(), LowerTable.end());

	ThompsonStack.push(UpperTable);
	return true;
}

void LexAnalyzer::EpsilonClosure(set<State*> startSet, set<State*>& result)
{
	stack<State*> UnVisitedStates;
	result = startSet;
	set<State*>::iterator iter;
	for (iter = startSet.begin(); iter != startSet.end(); ++iter)
	{
		UnVisitedStates.push(*iter);
	}

	while (!UnVisitedStates.empty())
	{
		State* curState = UnVisitedStates.top();
		UnVisitedStates.pop();

		vector<State*> epsilonStates;
		curState->GetTransition(EPSILON, epsilonStates);

		vector<State*>::iterator epsilonItr;

		for (epsilonItr = epsilonStates.begin(); epsilonItr != epsilonStates.end(); ++epsilonItr)
		{
			if (result.find(*epsilonItr) == result.end())
			{
				result.insert(*epsilonItr);
				UnVisitedStates.push(*epsilonItr);
			}
		}
	}
}

void LexAnalyzer::Move(char chInput, set<State*> NFAState, set<State*>& Result)
{
	Result.clear();
	set<State*>::iterator iter;
	for (iter = NFAState.begin(); iter != NFAState.end(); ++iter)
	{
		vector<State*> States;
		(*iter)->GetTransition(chInput, States);
		for (int index = 0; index < (int)States.size(); ++index)
		{
			Result.insert(States[index]);
		}
	}
}

void LexAnalyzer::NFAtoDFA()
{
	set<State*> NFAStartStateSet;
	NFAStartStateSet.insert(NFATable[0]);

	set<State*> DFAStartStateSet;
	EpsilonClosure(NFAStartStateSet, DFAStartStateSet);

	NextStateID = 0;
	State* DFAStartState = new State(DFAStartStateSet, NextStateID++);

	DFATable.push_back(DFAStartState);

	vector<State*> UnVisitedStates;
	UnVisitedStates.push_back(DFAStartState);
	while (!UnVisitedStates.empty())
	{
		State* CurDFAState = UnVisitedStates[UnVisitedStates.size() - 1];
		UnVisitedStates.pop_back();

		set<char>::iterator iter;
		for (iter = InputSet.begin(); iter != InputSet.end(); ++iter)
		{
			set<State*> MoveRes, EpsilonClosureRes;

			Move(*iter, CurDFAState->GetNFAState(), MoveRes);
			EpsilonClosure(MoveRes, EpsilonClosureRes);

			set<State*>::iterator MoveResItr;
			set<State*>::iterator EpsilonClosureResItr;

			bool bFound = false;
			State* s = NULL;
			for (int i = 0; i < (int)DFATable.size(); ++i)
			{
				s = DFATable[i];
				if (s->GetNFAState() == EpsilonClosureRes)
				{
					bFound = true;
					break;
				}
			}
			if (!bFound)
			{
				State* U = new State(EpsilonClosureRes, NextStateID++);
				UnVisitedStates.push_back(U);
				DFATable.push_back(U);
				CurDFAState->AddTransition(*iter, U);
			}
			else
			{
				CurDFAState->AddTransition(*iter, s);
			}
		}
	}
}

bool LexAnalyzer::Matching(string s)
{
	State* pState = DFATable[0];
	vector<State*> Transition;
	for (int i = 0; i < s.size(); i++)
	{
		char CurrChar = s[i];
		pState->GetTransition(CurrChar, Transition);
		if (Transition.empty())
			return false;
		pState = Transition[0];
	}
	if (pState->Accept)
		return true;

	return false;
}

void LexAnalyzer::Scanner() {
	int first = 0;
	while (first < str.size()) {
		char currentChar = str[first];

		if (isspace(currentChar)) {
			first++;
			continue;
		}

		string tokenValue;
		string tokenType;

		unordered_set<string> keywords = {
			"int", "float", "double", "char", "sreing", "void",
			"if", "else", "while", "for", "return", "continue",
			"const", "using", "namespace", "include", "true", "false"
		};

		if (isalpha(currentChar)) {
			while (isalpha(currentChar) || isdigit(currentChar) || currentChar == '_') {
				tokenValue += currentChar;
				first++;
				currentChar = str[first];
			}
			if (keywords.find(tokenValue) != keywords.end()) {
				tokenType = "KEYWORD";
			}
			else {
				tokenType = "IDENTIFIER";
			}
		}
		else if (isdigit(currentChar)) {
			while (isdigit(currentChar)) {
				tokenValue += currentChar;
				first++;
				currentChar = str[first];
			}
			tokenType = "NUMBER";
		}
		else if (currentChar == '<' && first + 1 < str.size() && str[first + 1] == '<') {
			tokenValue = "<<";
			tokenType = "OPERATOR";
			first += 2;
		}
		else if (currentChar == '>' && first + 1 < str.size() && str[first + 1] == '>') {
			tokenValue = ">>";
			tokenType = "OPERATOR";
			first += 2;
		}
		else if (currentChar == '<' && first + 1 < str.size() && isspace(str[first + 1])) {
			tokenValue = currentChar;
			tokenType = "OPERATOR";
			first++;
		}
		else if (currentChar == '+' || currentChar == '-' || currentChar == '*' || currentChar == '/' || currentChar == '=') {
			tokenValue = currentChar;
			tokenType = "OPERATOR";
			first++;
		}
		else if (currentChar == '#') {
			tokenValue = "#";
			tokenType = "PREPROCESSOR_DIRECTIVE";
			first++;
		}
		else {
			tokenValue = currentChar;
			tokenType = "SPECIALSYMBOL";
			first++;
		}

		Token newToken;
		newToken.value = tokenValue;
		newToken.type = tokenType;
		Tokens.push_back(newToken);
	}
}

void LexAnalyzer::Output()
{
	fstream f;
	f.open("output.txt", ios::out);
	for (int i = 0; i < Tokens.size(); i++)
	{
		f << Tokens[i].value << "\t" << Tokens[i].type << "\n";
	}
	f.close();
}

int main()
{
	LexAnalyzer LA;

	LA.LoadInputFile();
	LA.InputInfixRE();
	LA.PreProcessInfixRE();
	LA.InfixREtoPostfixRE();
	LA.PostfixREtoNFA();
	LA.NFAtoDFA();
	LA.Scanner();
	LA.Output();
}